Background: A comprehensive, HIV prevention programme (Projet Sida1/2/3) was implemented among female sex workers (FSWs) in Cotonou, Benin, in 1993 following which condom use among FSWs increased threefold between 1993 and 2008 while FSW HIV prevalence declined from 53.3% to 30.4%. Objective: Estimate the potential impact of the intervention on HIV prevalence/incidence in FSWs, clients and the general population in Cotonou, Benin. Methods and Findings: A transmission dynamics model parameterised with setting-specific bio-behavioural data was used within a Bayesian framework to fit the model and simulate HIV transmission in the high and low-risk population of Cotonou and to estimate HIV incidence and infections averted by SIDA1/2/3. Our model results suggest that prior to SIDA1/2/3 commercial sex had contributed directly or indirectly to 93% (84–98%) of all cumulative infections and that the observed decline in FSWs HIV prevalence was more consistent with the self-reported post-intervention increase in condom use by FSWs than a counterfactual assuming no change in condom use after 1993 (CF-1). Compared to the counterfactual (CF-1), the increase in condom use may have prevented 62% (52–71%) of new HIV infections among FSWs between 1993 and 2008 and 33% (20–46%) in the overall population. Conclusions: Our analysis provides plausible evidence that the post-intervention increase in condom use during commercial sex significantly reduced HIV prevalence and incidence among FSWs and general population. Sex worker interventions can be effective even in medium HIV prevalence epidemics and need to be sustained over the long-term.